#include <algorithm>
#include <cstdio>
#include <iostream>

using std::cin;
using std::cout;

typedef long long LL;
typedef unsigned int uint;

const int maxn = 5e1 + 3, slim = 1 << 12;

uint e[maxn], f[maxn][slim];

inline bool check(LL state, int n) {
	int popcnt = 0, flag = true;
	for (int i = 0; i < n; ++i) {
		if ((state >> i) & 1) {
			popcnt++;
			if ((e[i] & state) == 0) flag = false;
		}
	}
	if (popcnt == 1) flag = true;
	return flag;
}

int main() {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		//if (a > b) std::swap(a, b);
		e[b] |= 1 << a;
		e[a] |= 1 << b;
	}
	//for (int i = 0; i < n; ++i) e[i] |= 1 << i;
	LL ans = 0;
	for (int i = 1, ilim = 1 << n; i < ilim; ++i) {
		if (check(i, n)) ans ^= 1;
	}
	/*f[1][0] = 1, f[1][1] = 1;
		int ans = 0;
		for (int i = 1; i <= n; ++i) {
		for (int s = 0; s < slim; ++s) {
		f[i + 1][s << 1] ^= f[i][s];
		if ((e[i + 1] >> 1) & s) f[i + 1][s << 1 | 1] ^= f[i][s];
		if (s & 1) ans ^= f[i][s];
		}
		}*/
	cout << ans;
	return 0;
}
